package org.example.utils;

import org.springframework.util.StringUtils;

import java.util.ArrayList;
import java.util.List;

/**
 *  字符串类 工具
 */
public class StringOperUtils {

    /**
     * 将source中的target替换成replaceStr
     * @param source
     * @param target
     * @param replaceStr
     * @return
     */
    public  String replaceAll(String source, String target, String replaceStr) {
        // 调用 《1、字符串匹配》获取target在source中匹配到的所有的初始下标位置
        List<Integer> indexList = findIndex(source, target);
        if (indexList.isEmpty()) {
            return source;
        }
        StringBuilder str = new StringBuilder();
        int length = source.length();
        int index = indexList.get(0);
        for (int i = 0, j = 0; i < length; i++) {
            char ch = source.charAt(i);
            if (i == index) {
                str.append(replaceStr);
                i += target.length() - 1;
                j++;
                if (j < indexList.size()) {
                    index = indexList.get(j);
                }
            } else {
                str.append(ch);
            }
        }
        return str.toString();
    }


    /**
     * 查找target在source中的所有匹配的初始下标位置
     * @param source 待查找的字符串
     * @param target 用于查找的目标字符串
     * @return
     */
    public List<Integer> findIndex(String source, String target){
        List<Integer> ans = new ArrayList<>();
        if (StringUtils.isEmpty(source) || StringUtils.isEmpty(target)) {
            return ans;
        }
        int s = source.length();
        int t = target.length();
        // 创建next数组
        int[] next = new int[t];
        for (int i = 1,j=0; i < t; i++) {
            while (j>0&&target.charAt(i)!=target.charAt(j)){
                j = next[j-1];
            }
            if (target.charAt(i) == target.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        // 匹配
        for (int i = 0,j=0; i < s; i++) {
            while (j>0&&source.charAt(i)!=target.charAt(j)){
                j = next[j-1];
            }
            if (source.charAt(i) == target.charAt(j)){
                j++;
            }
            if (j == t){
                ans.add(i-t+1);  // 相比KMP仅在此处改动:每当匹配时记录初始位置下标
                j = 0;
            }
        }
        return ans;
    }

}
